package database.datastructure;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BPlusTree<K extends Comparable<K>,V> implements Serializable{
	private Node<K,V> root;
	private int size = 8;
	private List<V> searchReturn = null;
	private String treeRep = "";
	/**
	 * The below two variables are used for generatedSortedList() for Threshold Impl --- Srivathsan
	 */
	private ArrayList<V> sortedValues = new ArrayList<V>();
	private HashMap<V,K> sortedMap = new HashMap<V,K>();
	
	public List<V> getSortedValues() {
		return sortedValues;
	}

	public Map<V, K> getSortedMap() {
		return sortedMap;
	}

	
	/**
	 * Useful for fixing the parents in the hierarchy, from information
	 * sent from child nodes. (this obj propagate bottom up)
	 * @author Sravan
	 *
	 */
	
	private class SearchReturnValue{
		
		public SearchReturnValue(Node<K, V> node, int start_position) {
			super();
			this.node = node;
			this.start_position = start_position;
		}
		public Node<K,V> node;
		public int start_position;
	}
	
	public BPlusTree(){
		root = new Node<K,V>(size);
	}
	
	private class InsertReturnValue{
		Node<K,V> rightPointer;
		K key_into_parent;
		/**
		 * @return the rightPointer
		 */
		public Node<K, V> getRightPointer() {
			return rightPointer;
		}
		/**
		 * @param rightPointer the rightPointer to set
		 */
		public void setRightPointer(Node<K, V> rightPointer) {
			this.rightPointer = rightPointer;
		}
		/**
		 * @return the key_into_parent
		 */
		public K getKey_into_parent() {
			return key_into_parent;
		}
		/**
		 * @param key_into_parent the key_into_parent to set
		 */
		public void setKey_into_parent(K key_into_parent) {
			this.key_into_parent = key_into_parent;
		}
	}
	
	public String newprintTree() {
		treeRep = "";
		newprint(root,0); 
		return treeRep;
	}
	
    private void newprint(Node<K,V> node,int level) {
    	String space="\t";		
    	if(!node.isALeafNode())
    	{
    		for(int k=0;k < node.getSearchKeys().size();k++)
    		{    			
    			newprint(node.getNodePointer(k),level+1);
    			String temp="";
    			for(int l=0;l<level;l++)
    				temp= temp+space ;
    			temp =  temp+node.getSearchKey(k) + "\n";
    			treeRep = treeRep + temp;
    			//newprint(node.getNodePointer(k));
    		}
    	    newprint(node.getNodePointer(node.getSearchKeys().size()),level+1);
    	}  
    	else
    	{
    		for (int j = 0; j < node.getSearchKeys().size(); j++) {    				
    			if (node.getSearchKey(j) != null) {
    				String temp="";
    				for(int l=0;l<level;l++)
        				temp=temp+space;
    				temp = temp+node.getSearchKey(j) + " " + node.getDataRecord(j) + "\n";
    				treeRep = treeRep + temp; 
    			}
    		}	
    	}   	
	}
    
	/* Used for printing the index 
	 * 
	 */
	
	public String printTree() {
		treeRep = "";
		print(root); 
		return treeRep;
	}
	
	private void print(Node<K,V> node) {
		if (node.isALeafNode())
		{
			for (int j = 0; j < node.getSearchKeys().size(); j++) {
				//System.out.println(node.getSearchKey(j));
				//System.out.println(node.getDataRecord(j));
				if (node.getSearchKey(j) != null) {
					String temp = "\t" + node.getSearchKey(j) + " " + node.getDataRecord(j) + "\n";
					treeRep = treeRep + temp; 
				}
			}
			Node<K,V> tempNode = node;
			boolean flag = true;
			while (flag) {
				if (tempNode.getNextLeafNode() != null) {
					Node<K,V> nextNode = tempNode.getNextLeafNode();
					for(int j = 0; j < nextNode.getSearchKeys().size(); j++){
						//System.out.println(nextNode.getSearchKey(j));
						//System.out.println(nextNode.getDataRecord(j));
						if (nextNode.getSearchKey(j) != null) {
							String temp = "\t" + nextNode.getSearchKey(j) + " " + nextNode.getDataRecord(j) + "\n";
							treeRep = treeRep + temp;
						}
					}
					if ((nextNode.getNextLeafNode() != null)) {
						tempNode = nextNode;
						flag = true;
					} else {
						flag = false;
					}
				} else {
					flag = false;
				}
			}
		} else {
			print(node.getNodePointer(0));
		}
	}
	/*public String printTree() {
		print(root); 
		return treeRep;
	}
	
	private void print(Node<K,V> node) {
		for (K k1:node.getSearchKeys()) {
			treeRep = treeRep + " " + k1;
		}
		if (node.isALeafNode())
		{
			for (int i = 0; i < node.getDataRecords().size(); i++) {
				if (i == 0) {
					//index = index + "\n";
				}
				treeRep = treeRep + " " + node.getDataRecord(i);
			}
		} else {
			for (int i = 0; i < node.getNodePointers().size(); i++) {
				if (i == 0) {
					treeRep = treeRep + "\n";
				}
				print(node.getNodePointer(i));
			}
		}
		treeRep = treeRep + "		";
	}*/
	
	/*public List<V> search(K key){
		List<V> list = new ArrayList<V>();
		SearchReturnValue val = search(root,key);
		Node<K,V> node = val.node;
		int pos = val.start_position;
		boolean end_of_list = false;
		while(node != null && !end_of_list){
			int idx = 0;
			for(K k:node.getSearchKeys()){
				if(idx < pos){ // only for the initial case.
					idx++;
					continue;
				}
				if(k.compareTo(key) == 0){
					list.add(node.getDataRecord(idx));
					idx++;
				}
				else{
					end_of_list = true;
					break;
				}
			}
			node = node.getNextLeafNode();
			pos = 0;
		}
		
		
		return list;
	}

	private SearchReturnValue search(Node<K,V> node, K key){
		if(node.isALeafNode()){
			int idx1 = 0;
			for(K k1:node.getSearchKeys()){
				if(key.compareTo(k1) == 0){
					// ADD_CODE TO RETURN A LIST TO SUPPORT OF DUPLICATE KEYS
					return new SearchReturnValue(node, idx1);
				}
				idx1++;
			}
			return new SearchReturnValue(null,-1);
		}
		else{
			int idx1 = 0;
			for(K k1:node.getSearchKeys()){
				if(key.compareTo(k1) < 0){
					break;
				}
				idx1++;
			}
			return search(node.getNodePointer(idx1),key);
		}
	}*/
	
	/**
	 * Added by Srivathsan for Threhold Implementation
	 */
	
	public void generateDecSortedList(){
		this.sortedValues = new ArrayList<V>();
		this.sortedMap = new HashMap<V,K>();
		generateDecSortedList(root);
	}

	private void generateDecSortedList(Node<K,V> node){
		if(node.isALeafNode()){
			
			for(int k1 = node.getSearchKeys().size()-1; k1 >= 0 ; k1--){
				this.sortedValues.add(node.getDataRecord(k1));
				this.sortedMap.put(node.getDataRecord(k1), node.getSearchKey(k1));
			}
			
			Node<K,V> tempNode = node;
			boolean flag = true;
			while (flag) {
				if (tempNode.getPrevLeafNode() != null) {
					Node<K,V> prevNode = tempNode.getPrevLeafNode();
					
					for(int k2 = prevNode.getSearchKeys().size()-1; k2 >= 0 ; k2--){
						this.sortedValues.add(prevNode.getDataRecord(k2));
						this.sortedMap.put(prevNode.getDataRecord(k2), prevNode.getSearchKey(k2));
					}
					
					if ((prevNode.getPrevLeafNode() != null)) {
						tempNode = prevNode;
						flag = true;
					} else {
						flag = false;
					}
				} else {
					flag = false;
				}
			}
		}
		else{
			int lastPtr = node.getSearchKeys().size()-1;
			generateDecSortedList(node.getNodePointer(lastPtr));
		}
	}

	
	
	public void generateIncSortedList(){
		this.sortedValues = new ArrayList<V>();
		this.sortedMap = new HashMap<V,K>();
		generateIncSortedList(root);
	}

	private void generateIncSortedList(Node<K,V> node){
		if(node.isALeafNode()){
			for(int k1 = 0; k1 < node.getSearchKeys().size() ; k1++){
				this.sortedValues.add(node.getDataRecord(k1));
				this.sortedMap.put(node.getDataRecord(k1), node.getSearchKey(k1));
			}
			
			Node<K,V> tempNode = node;
			boolean flag = true;
			while (flag) {
				if (tempNode.getNextLeafNode() != null) {
					Node<K,V> nextNode = tempNode.getNextLeafNode();
					
					for(int k2 = 0; k2 < nextNode.getSearchKeys().size() ; k2++){
						this.sortedValues.add(nextNode.getDataRecord(k2));
						this.sortedMap.put(nextNode.getDataRecord(k2), nextNode.getSearchKey(k2));
					}
					
					if ((nextNode.getNextLeafNode() != null)) {
						tempNode = nextNode;
						flag = true;
					} else {
						flag = false;
					}
				} else {
					flag = false;
				}
			}
		}
		else{
			generateIncSortedList(node.getNodePointer(0));
		}
	}
	
	
	public List<V> search(K key){
		this.searchReturn = new ArrayList<V>();
		return search(root,key);
	}

	private List<V> search(Node<K,V> node, K key){
		if(node.isALeafNode()){
			int idx1 = 0;
			for(K k1:node.getSearchKeys()){
				if(key.compareTo(k1) == 0){
					//System.out.println("Adding "+node.getDataRecord(idx1));
					this.searchReturn.add(node.getDataRecord(idx1));
				}
				idx1++;
			}
			Node<K,V> tempNode = node;
			boolean flag = true;
			while (flag) {
				if (tempNode.getNextLeafNode() != null) {
					Node<K,V> nextNode = tempNode.getNextLeafNode();
					int rcrdCntr = 0;
					for(K k1:nextNode.getSearchKeys()){
						if (key.compareTo(k1) == 0){
							//System.out.println("Adding 1 "+nextNode.getDataRecord(rcrdCntr));
							this.searchReturn.add(nextNode.getDataRecord(rcrdCntr));
						}
						//sravan_test_code
						else{
							return this.searchReturn;
						}
						rcrdCntr++;
					}
					
					//sravan_test_comment
					tempNode = nextNode;
					/*if ((nextNode.getNextLeafNode() != null)) {
						Node<K,V> nextNextNode = nextNode.getNextLeafNode();
						int tmpCntr = 0;
						for (K k1:nextNextNode.getSearchKeys()){
							if (key.compareTo(k1) == 0){
								tmpCntr++;
							}
							//sravan_test_code
							else{
								return this.searchReturn;
							}
						}
						if (tmpCntr == 0)
							flag = false;
						else  {
							tempNode = nextNode;
							flag = true;
						}
					} else {
						flag = false;
					}*/
						
				} else {
					flag = false;
				}
			}
			return searchReturn;
		}
		else{
			int idx1 = 0;
			for(K k1:node.getSearchKeys()){
				if(key.compareTo(k1) <= 0) {
					//System.out.println("Traversed Key : "+k1);
					break;
				}
				idx1++;
			}
			return search(node.getNodePointer(idx1),key);
		}
	}
	
	public void insert(K key, V value){
		insert(root, key, value);
	}
	
	public void insert(Node<K,V> node, K key, V value){
		InsertReturnValue irv = recursiveInsert(node, key, value);
		if(irv != null){
			//fix the root;
			Node<K,V> new_node = new Node<K, V>(this.size);
			new_node.setLeafNode(false);
			new_node.addSearchKey(0, irv.getKey_into_parent());
			new_node.addNodePointer(0,node);
			new_node.addNodePointer(1,irv.getRightPointer());
			this.root = new_node;
		}
	}
	
	public void printRecordsOnBottomLevel_Reverse(){
		Node<K,V> rightMost = getRightMostLeafNode(root);
		while(rightMost != null){
			for(V val:rightMost.getDataRecords())
				System.out.print(val.toString()+",");
			rightMost = rightMost.getPrevLeafNode();
			System.out.print(" | ");
		}		
	}
	
	private Node<K,V> getRightMostLeafNode(Node<K,V> node){
		if(node.isALeafNode()){
			return node;
			//return node.getNodePointer(node.numberOfNodePointers()-1);
		}
		else{
			return getRightMostLeafNode(node.getNodePointer(node.numberOfNodePointers()-1));
		}
	}

	public void printRecordsOnBottomLevel_Forward(){
		Node<K,V> leftMost = getLeftMostLeafNode(root);
		while(leftMost != null){
			for(V val:leftMost.getDataRecords())
				System.out.print(val.toString()+",");
			leftMost = leftMost.getNextLeafNode();
			System.out.print(" | ");
		}		
	}
	
	private Node<K,V> getLeftMostLeafNode(Node<K,V> node){
		if(node.isALeafNode()){
			return node;
			//return node.getNodePointer(0);
		}
		else{
			return getLeftMostLeafNode(node.getNodePointer(0));
		}
	}

	private InsertReturnValue recursiveInsert(Node<K,V> node, K key, V value){
		if(node.isALeafNode()){
			if(node.isFull()){
				//split and fix and return;
				List<K> keyList = node.getSearchKeys();
				
				int idx2 = 0;
				for(K k3:keyList){
					if(key.compareTo(k3) < 0){
						break;
					}
					idx2++;
				}
				/*
				 * There will be size+1 elements after below steps.
				 * split them and send to parent.
				 */
				node.addSearchKey(idx2,key);
				node.addDataRecord(idx2, value);
				
				//---
				Node<K,V> new_child = new Node<K, V>(this.size);
				for(int i=0;i<this.size/2 + 1;i++){ // repeat 4+1 times.
					new_child.addSearchKey(node.removeSearchKey(this.size/2)); // 5 for this project
					new_child.addDataRecord(node.removeDataRecord(this.size/2));
				}
				
				//set next & prev child leafNodes
				if(node.getNextLeafNode() != null)
					node.getNextLeafNode().setPrevLeafNode(new_child);
				new_child.setNextLeafNode(node.getNextLeafNode());
				new_child.setPrevLeafNode(node);
				node.setNextLeafNode(new_child);
				
				
				//node.setLeafNode(false);
				InsertReturnValue irv3 = new InsertReturnValue();
				irv3.setKey_into_parent(new_child.getSearchKey(0)); //first key on right child
				irv3.setRightPointer(new_child);
				return irv3;
				//---
				
			}
			else{
				int idx2 = 0;
				for(K k:node.getSearchKeys()){
					if(key.compareTo(k) < 0){
						break;
					}
					idx2++;
				}
				node.addSearchKey(idx2, key);
				node.addDataRecord(idx2, value);
				//nothing to fix above.
				return null;
			}
		}
		else{
			int index = 0;
			for(K k1:node.getSearchKeys()){
				/*
				 * <= or <  -- can be one consideration.
				 */
				if(key.compareTo(k1) < 0){
					break;
				}
				index++;
			}
			Node<K,V> node1 = node.getNodePointer(index);
			InsertReturnValue irv = recursiveInsert(node1,key,value);
			if(irv == null){
				return null;
			}
			else{
				//fix and return;
				//index still holds the NodePointer location.
				if(node.isFull()){
				//split again and return;
					//Just add key and link.
					List<K> keyList = node.getSearchKeys();
					K k2 = irv.getKey_into_parent();
					int idx1 = 0;
					for(K k3:keyList){
						if(k2.compareTo(k3) < 0){
							break;
						}
						idx1++;
					}
					/*
					 * adding elements beyond capacity
					 * Other temp variable can be used, (little more work)
					 */					
					node.addSearchKey(idx1,k2);
					node.addNodePointer(idx1+1, irv.getRightPointer());
					/*
					 * now there are size+1 keys & size+2 nodePointers;
					 * or for size =8, 9 keys & 10 nodePointers 
					 */
					Node<K,V> new_child = new Node<K, V>(this.size);
					//node.setLeafNode(false);
					for(int i=0;i<this.size/2 + 1;i++){
						new_child.addSearchKey(node.removeSearchKey(this.size/2)); // 5 for this project
						new_child.addNodePointer(node.removeNodePointer(this.size/2 +1));
					}
					//new_child.addNodePointer(node.removeNodePointer(this.size/2 +1));
					new_child.setLeafNode(false);
					InsertReturnValue irv2 = new InsertReturnValue();
					irv2.setKey_into_parent(new_child.removeSearchKey(0));
					irv2.setRightPointer(new_child);
					return irv2;
				}
				else{
					// Fixed, nothing to fix in upper level.
					node.addSearchKey(index, irv.getKey_into_parent());
					node.addNodePointer(index+1, irv.getRightPointer());
					return null;
				}

			}
		}
	}
	
	public void deleteKey(K key){
		//Search first.
		recursiveDelete(root,key,null,-1);
	}

	// to be used to fix parents recursively
	private class DeleteReturnValue{
		int key_position_to_remove;

		public DeleteReturnValue(int key_position_to_remove) {
			super();
			this.key_position_to_remove = key_position_to_remove;
		}

	}

	private DeleteReturnValue recursiveDelete(Node<K,V> node, K key, Node<K,V> parent, int index_in_parent){
		if(node.isALeafNode()){
			int idx1 = 0;
			for(K k1:node.getSearchKeys()){
				if(key.compareTo(k1) == 0){
					break;
				}
				idx1++;
			}
			if(idx1 == node.getSearchKeys().size()){
				// NO_RECORDS_TO _DELETE
				return null;
			}
			else{
				node.removeSearchKey(idx1);
				node.removeDataRecord(idx1);
				if(node.getSearchKeys().size() >= this.size/2 || node == root){ // nothing to do in root.
					// DELETE_COMFORTABLY AND NOTHING_TO_FIX
					return null;
				}
				else{
					// IF_BORROW_POSSIBLE, BORROW
					if(index_in_parent == 0){ // MERGE_POSSIBLE WITH RIGHT ONLY
						Node<K,V> right_sibling = parent.getNodePointer(index_in_parent+1);
						if(right_sibling.getSearchKeys().size() > this.size/2){
							// move Key_Value pair
							K m_key = right_sibling.removeSearchKey(0);
							V m_Value = right_sibling.removeDataRecord(0);
							int no_of_keys = node.no_of_keys();
							node.addSearchKey(no_of_keys, m_key);
							node.addDataRecord(no_of_keys,m_Value);
							// Update parent key to first key in right node. 
							// this code can be moved to parent. 
							parent.removeSearchKey(0);
							parent.addSearchKey(0, right_sibling.getSearchKey(0));
							return null;
						}
						else{
							// TODO IT MUST BE MERGED
							int merged_no_of_keys = node.no_of_keys();
							int no_of_keys = right_sibling.no_of_keys();
							for(int i=0;i<no_of_keys;i++){
								node.addSearchKey(merged_no_of_keys, right_sibling.removeSearchKey(0));
								node.addDataRecord(merged_no_of_keys, right_sibling.removeDataRecord(0));
								merged_no_of_keys++;
							}
							return new DeleteReturnValue(0);
						}
					}
					else if(index_in_parent == this.size){ // MERGE_POSSIBLE WITH LEFT ONLY
						Node<K,V> left_sibling = parent.getNodePointer(index_in_parent-1);
						if(left_sibling.getSearchKeys().size() > this.size/2){
							// move Key_Value pair
							int no_of_keys = left_sibling.no_of_keys();
							K m_key = left_sibling.removeSearchKey(no_of_keys-1);
							V m_Value = left_sibling.removeDataRecord(no_of_keys-1);
							node.addSearchKey(0, m_key);
							node.addDataRecord(0,m_Value);
							// Update parent key to first key in right node. 
							// this code can be moved to parent. 
							parent.removeSearchKey(index_in_parent-1); //7th
							parent.addSearchKey(index_in_parent-1, node.getSearchKey(0));
							return null;
						}
						else{
							// TODO IT MUST BE MERGED
							int no_of_keys = node.no_of_keys();
							int merged_no_of_keys = left_sibling.no_of_keys();
							for(int i=0;i<no_of_keys;i++){
								left_sibling.addSearchKey(merged_no_of_keys, node.removeSearchKey(0));
								left_sibling.addDataRecord(merged_no_of_keys, node.removeDataRecord(0));
								merged_no_of_keys++;
							}
							return new DeleteReturnValue(index_in_parent-1); //7th
						}


					}
					else{ // MERGE_POSSIBLE ON BOTH SIDES
						// TRY BORROWING FIRST, IF DOESN'T WORK, DO MERGE. ALWAYS (LEFT first)

						Node<K,V> left_sibling = parent.getNodePointer(index_in_parent-1);
						boolean merge_left = false;
						boolean merge_right = false;
						if(left_sibling.getSearchKeys().size() > this.size/2){
							// move Key_Value pair
							int no_of_keys = left_sibling.no_of_keys();
							K m_key = left_sibling.removeSearchKey(no_of_keys -1);
							V m_Value = left_sibling.removeDataRecord(no_of_keys-1);
							node.addSearchKey(0, m_key);
							node.addDataRecord(0,m_Value);
							// Update parent key to first key in right node. 
							// this code can be moved to parent. 
							parent.removeSearchKey(index_in_parent-1);
							parent.addSearchKey(index_in_parent-1, node.getSearchKey(0));
							return null;
						}
						else{
							merge_left = true;
						}

						//System.out.println("--> INDEX_IN_PATIENT : "+index_in_parent + " --- "+parent.getNodePointers().size() + " --- "+parent.getSearchKeys().size());
						
						boolean ignore_right = false;
						if(index_in_parent+1 >= parent.getNodePointers().size()){ // RIGHT DOENS'T EXIST
							ignore_right = true;
						}

						Node<K,V> right_sibling = null;
						try{
							right_sibling = parent.getNodePointer(index_in_parent+1);
						}
						catch(IndexOutOfBoundsException e){
							//System.out.println("EXCEPTION HANDLED");
						}

						if(!ignore_right && right_sibling.getSearchKeys().size() > this.size/2){
							// move Key_Value pair
							K m_key = right_sibling.removeSearchKey(0);
							V m_Value = right_sibling.removeDataRecord(0);
							int no_of_keys = node.no_of_keys();
							node.addSearchKey(no_of_keys, m_key);
							node.addDataRecord(no_of_keys,m_Value);
							// Update parent key to first key in right node. 
							// this code can be moved to parent. 
							parent.removeSearchKey(index_in_parent);
							parent.addSearchKey(index_in_parent, right_sibling.getSearchKey(0));
							return null;
						}
						else{
							merge_right = true;
						}

						// BORROW DIDN'T WORK, SO MERGE NOW, left and then right. (IDEALLY ONLY LEFT CODE IS SUFFICIENT, 
						// RIGHT CAN BE USED TO DO SOME OPTIMIZATION WHEN NEEDED. 
						if(merge_left){
							// TODO IT MUST BE MERGED
							int no_of_keys = node.no_of_keys();
							int merged_no_of_keys = left_sibling.no_of_keys();
							for(int i=0;i<no_of_keys;i++){
								left_sibling.addSearchKey(merged_no_of_keys, node.removeSearchKey(0));
								left_sibling.addDataRecord(merged_no_of_keys, node.removeDataRecord(0));
								merged_no_of_keys++;
							}
							return new DeleteReturnValue(index_in_parent-1);
						}


						if(!ignore_right && merge_right){
							// TODO IT MUST BE MERGED
							int merged_no_of_keys = node.no_of_keys();
							int no_of_keys = right_sibling.no_of_keys();
							for(int i=0;i<no_of_keys;i++){
								node.addSearchKey(merged_no_of_keys, right_sibling.removeSearchKey(0));
								node.addDataRecord(merged_no_of_keys, right_sibling.removeDataRecord(0));
								merged_no_of_keys++;
							}
							return new DeleteReturnValue(index_in_parent);
						}
					}
					// ELSE_MERGE_AND_FIX UP
				}
			}

		}
		else{
			int idx1 = 0;
			for(K k1:node.getSearchKeys()){
				if(key.compareTo(k1) < 0){
					break;
				}
				idx1++;
			}
			DeleteReturnValue drv = recursiveDelete(node.getNodePointer(idx1), key, node, idx1);
			if(drv == null){
				// Already fixed, nothing to fix in parent.
				return null;
			}

			// SPECIAL CASE FOR ROOT MUST BE HANDLED
			if(parent == null){
				if(node.no_of_keys() == 1){ // 1 before delete
					root = node.getNodePointer(0);
					return null;
				}
				node.removeSearchKey(drv.key_position_to_remove);
				node.removeNodePointer(drv.key_position_to_remove+1);
				if(node.no_of_keys() == 1){ // after delete
					if(node.getNodePointer(0).no_of_keys() + node.getNodePointer(0).no_of_keys() <= this.size){
						// MOVE BOTH TO ROOT
						Node<K,V> left = node.getNodePointer(0);
						Node<K,V> right = node.getNodePointer(1);
						// right is also a leaf. why?
						int left_keys = left.no_of_keys();
						int right_keys = right.no_of_keys();
						for(int i=0;i<right_keys;i++){
							node.addSearchKey(left_keys, right.removeSearchKey(0));
							if(left.isALeafNode()){
								node.addDataRecord(left_keys, right.removeDataRecord(0));
							}
							else{
								node.addNodePointer(left_keys+1, right.removeNodePointer(1));
							}
							left_keys++;
						}
						root = left;
					}
				}
				return null;
			}

			//****************************************************
			// TODO
			node.removeSearchKey(drv.key_position_to_remove);
			node.removeNodePointer(drv.key_position_to_remove+1);
			if(node.getSearchKeys().size() >= this.size/2){
				// DELETE_COMFORTABLY AND NOTHING_TO_FIX at parent
				return null;
			}
			else{
				// IF_BORROW_POSSIBLE, BORROW
				if(index_in_parent == 0){ // MERGE_POSSIBLE WITH RIGHT ONLY
					Node<K,V> right_sibling = parent.getNodePointer(index_in_parent+1);
					if(right_sibling.getSearchKeys().size() > this.size/2){
						// move Key_Value pair
						K m_key = right_sibling.removeSearchKey(0);
						Node<K,V> m_node = right_sibling.removeNodePointer(0);
						// this is different from leafNode case.
						int no_of_keys = node.no_of_keys();
						node.addSearchKey(no_of_keys, parent.getSearchKey(index_in_parent));
						node.addNodePointer(no_of_keys+1,m_node); // +1 again for the same reason, node = keys + 1
						// Update parent key to first key in right node. 
						// this code can be moved to parent. 
						parent.removeSearchKey(0);
						parent.addSearchKey(0, m_key);
						return null;
					}
					else{
						// IT MUST BE MERGED : NOTE: first pointer(0) on the right is not required, 
						//		as last pointer on left and second pointer(1) on right together can handle this data.
						int merged_no_of_keys = node.no_of_keys();
						int no_of_keys = right_sibling.no_of_keys();
						node.addSearchKey(parent.getSearchKey(index_in_parent));
						node.addNodePointer(merged_no_of_keys+1, right_sibling.removeNodePointer(0));
						merged_no_of_keys++;
						for(int i=0;i<no_of_keys;i++){
							node.addSearchKey(merged_no_of_keys, right_sibling.removeSearchKey(0));
							node.addNodePointer(merged_no_of_keys+1, right_sibling.removeNodePointer(0));
							merged_no_of_keys++;
						}
						return new DeleteReturnValue(0);
					}
				}
				else if(index_in_parent == this.size){ // MERGE_POSSIBLE WITH LEFT ONLY
					Node<K,V> left_sibling = parent.getNodePointer(index_in_parent-1);
					if(left_sibling.getSearchKeys().size() > this.size/2){
						// move Key_Value pair
						K m_key = left_sibling.removeSearchKey(left_sibling.no_of_keys()-1);
						Node<K,V> m_node = left_sibling.removeNodePointer(left_sibling.no_of_keys()); // -1 not required as nodes = 1+keys
						node.addSearchKey(0, parent.getSearchKey(index_in_parent-1));
						node.addNodePointer(0,m_node);
						// Update parent key to first key in right node. 
						// this code can be moved to parent. 
						parent.removeSearchKey(index_in_parent-1); //7th
						parent.addSearchKey(index_in_parent-1, m_key);
						return null;
					}
					else{
						// IT MUST BE MERGED
						int no_of_keys = node.no_of_keys();
						int merged_no_of_keys = left_sibling.no_of_keys();
						node.addSearchKey(parent.getSearchKey(index_in_parent-1));
						node.addNodePointer(merged_no_of_keys+1, left_sibling.removeNodePointer(0));
						merged_no_of_keys++;
						for(int i=0;i<no_of_keys;i++){
							left_sibling.addSearchKey(merged_no_of_keys, node.removeSearchKey(0));
							left_sibling.addNodePointer(merged_no_of_keys+1, node.removeNodePointer(1));
							merged_no_of_keys++;
						}
						return new DeleteReturnValue(index_in_parent-1); //7th
					}


				}
				else{ // MERGE_POSSIBLE ON BOTH SIDES
					// TRY BORROWING FIRST, IF DOESN'T WORK, DO MERGE. ALWAYS (LEFT first)
					Node<K,V> left_sibling = parent.getNodePointer(index_in_parent-1);
					boolean merge_left = false;
					boolean merge_right = false;
					if(left_sibling.getSearchKeys().size() > this.size/2){
						// move Key_Value pair
						K m_key = left_sibling.removeSearchKey(left_sibling.no_of_keys()-1);
						Node<K,V> m_node = left_sibling.removeNodePointer(left_sibling.no_of_keys()); // ge the last node pointer
						node.addSearchKey(0, parent.getSearchKey(0));
						node.addNodePointer(0,m_node);
						// Update parent key to first key in right node. 
						// this code can be moved to parent. 
						parent.removeSearchKey(index_in_parent-1);
						parent.addSearchKey(index_in_parent-1, m_key);
						return null;
					}
					else{
						merge_left = true;
					}

					boolean ignore_right = false;
					if(index_in_parent+1 >= parent.getNodePointers().size()){ // RIGHT DOENS'T EXIST
						ignore_right = true;
					}

					Node<K,V> right_sibling = null;
					try{
						right_sibling = parent.getNodePointer(index_in_parent+1);
					}
					catch(IndexOutOfBoundsException e){
						//System.out.println("EXCEPTION HANDLED");
					}
					if(!ignore_right && right_sibling.getSearchKeys().size() > this.size/2){
						// move Key_Value pair
						K m_key = right_sibling.removeSearchKey(0);
						Node<K,V> m_node = right_sibling.removeNodePointer(0);
						int no_of_keys = node.no_of_keys();
						node.addSearchKey(no_of_keys, parent.getSearchKey(index_in_parent));
						node.addNodePointer(no_of_keys+1, m_node);
						// Update parent key to first key in right node. 
						// this code can be moved to parent. 
						parent.removeSearchKey(index_in_parent);
						parent.addSearchKey(index_in_parent, m_key);
						return null;
					}
					else{
						merge_right = true;
					}

					// BORROW DIDN'T WORK, SO MERGE NOW, left and then right. (IDEALLY ONLY LEFT CODE IS SUFFICIENT, 
					// RIGHT CAN BE USED TO DO SOME OPTIMIZATION WHEN NEEDED. 
					if(merge_left){
						// IT MUST BE MERGED
						int no_of_keys = node.no_of_keys();
						int merged_no_of_keys = left_sibling.no_of_keys();
						// NEW_CODE
						System.out.println("--> merged_no_of_keys+1 : "+(merged_no_of_keys+1) + " --- "+node.getNodePointers().size() + " --- "+parent.getSearchKeys().size());
						left_sibling.addSearchKey(parent.getSearchKey(index_in_parent-1));
						left_sibling.addNodePointer(merged_no_of_keys+1, node.removeNodePointer(0));
						merged_no_of_keys++;
						for(int i=0;i<no_of_keys;i++){
							left_sibling.addSearchKey(merged_no_of_keys, node.removeSearchKey(0));
							left_sibling.addNodePointer(merged_no_of_keys+1, node.removeNodePointer(0));
							merged_no_of_keys++;
						}
						return new DeleteReturnValue(index_in_parent-1);
					}


					if(!ignore_right && merge_right){
						// IT MUST BE MERGED
						int merged_no_of_keys = node.no_of_keys();
						int no_of_keys = right_sibling.no_of_keys();
						// NEW_CODE
						node.addSearchKey(parent.getSearchKey(index_in_parent));
						node.addNodePointer(merged_no_of_keys+1, left_sibling.removeNodePointer(0));
						merged_no_of_keys++;
						for(int i=0;i<no_of_keys;i++){
							node.addSearchKey(merged_no_of_keys, right_sibling.removeSearchKey(0));
							node.addNodePointer(merged_no_of_keys+1, right_sibling.removeNodePointer(1));
							merged_no_of_keys++;
						}
						return new DeleteReturnValue(index_in_parent);
					}
				}
				// ELSE_MERGE_AND_FIX UP
			}
			// TODO MARKER	
			//****************************************************

			//fix parent here.
		}
		return null;
	}
}
